package arithmetic.demo13;


import java.util.*;

/**
 * 题目： 优先级队列_最后一块石头的重量
 */

class Solution {
    public int lastStoneWeight(int[] stones) {
        int n = stones.length;
        // 建立大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->{
            return b-a;
        });



        // 先一起加入
        for(int i =0; i<n; i++) {
            queue.add(stones[i]);
        }  

        // 对大根堆操作
        while(queue.size() > 1) {
            int num1 = queue.poll(), num2= queue.poll();
            // 比较进行入队列
            if(num1 > num2) {
                queue.add(num1 - num2);
            } else if(num1 < num2) {
                queue.add(num2 - num1);
            }
        }

        // 分情况返回结果
        return queue.size() == 0 ? 0 : queue.poll();
    }
}





   class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


/**
 * 队列_在每个树行中找出最大值
 */

class Solution1 {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        // 添加根节点
        queue.add(root);
        while(!queue.isEmpty()) {
            // 处理本层的数据
            int sz = queue.size();
            int max = Integer.MIN_VALUE;
            for(int i =0; i<sz; i++) {
                //    查找最大值
                TreeNode node = queue.poll();
                max = Math.max(node.val, max);
                // 添加下一层的孩子节点
                if(node.left != null) {
                    queue.add(node.left);
                }

                if(node.right != null) {
                    queue.add(node.right);
                }
            }

            // 将该层的最大值添加进结果中
            ret.add(max);
        }


        return ret;
    }
}


/**
 * 题目: 优先级队列_前k个高频单词
 */



class Solution2 {
    public List<String> topKFrequent(String[] words, int k) {
        int n = words.length;
        Map<String, Integer> hash = new HashMap<>();

        // 开始哈希统计个数
        for(int i =0; i<n; i++) {
            hash.put(words[i], hash.getOrDefault(words[i],0) + 1);
        }

        // 先建立大根堆
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>((a,b)->{
            // 如果次数相同就返回字符串小的
            if(b.getValue() == a.getValue()) {
                return a.getKey().compareTo(b.getKey());
            }
            // 否则就返回次数大的
            return b.getValue()-a.getValue();
        });

        // 开始遍历
        for(Map.Entry<String, Integer> tmp: hash.entrySet()) {
            queue.add(tmp);
        }

        List<String> ret =new ArrayList<>();
        for(int i =0; i<k ; i++) {
            ret.add(queue.poll().getKey());
        }


        return ret;

    }
}

/**
 * 题目: 优先级队列_TOPk问题_数据流中第k大的元素
 */



class KthLargest {
    PriorityQueue<Integer> queue ;
    int sz ;
    public KthLargest(int k, int[] nums) {
        sz = k;
        int n = nums.length;
        // 建立小根堆
        queue = new PriorityQueue<>((a,b)->{
            return a-b;
        });

        if(n >= k) {
            // 填加k 个元素进行队列
            for(int i = 0; i < k; i++) {
                queue.add(nums[i]);
            }
        } else {
            for(int i = 0;i<n; i++) {
                queue.add(nums[i]);
            }
        }


        // 开始更新
        for(int i = k ; i<n; i++) {
            // 遇到小的才更新
            int num = queue.peek();
            if(nums[i] >= num) {
                queue.poll();
                queue.add(nums[i]);
            }
        }

    }

    public int add(int val) {
        if(queue.size() < sz) {
            queue.add(val);
            return  queue.peek();
        }
        int num = queue.peek();

        if(val >= num) {
            queue.poll();
            queue.add(val);
        }

        return queue.peek();
    }
}


/**
 * 题目: 优先级队列_数据流的中位数
 */



class MedianFinder {
    PriorityQueue<Integer> minQueue;
    PriorityQueue<Integer> maxQueue;
    public MedianFinder() {
        // 实例化大小根堆
        maxQueue = new PriorityQueue<>((a,b) -> {
            return b - a;
        });

        minQueue = new PriorityQueue<>((a, b) -> {
            return a - b;
        });
    }

    public void addNum(int num) {
        // 如果为空 , 直接加入
        if(maxQueue.isEmpty()) {
            maxQueue.add(num);
            return ;
        }

        int n = maxQueue.size(), m = minQueue.size();
        // 开始分情况讨论
        if(m == n) {
            int tmp = maxQueue.peek();
            // 如果这个数小于大根堆的元素直接入大根堆
            if(num <= tmp) {
                maxQueue.add(num);
            } else {
                // 否则先入小根堆
                // 然后把小根堆队顶元素给大根堆
                minQueue.add(num);
                maxQueue.add(minQueue.poll());
            }
        } else if(n == m + 1) {
            // 如果这个数小于大根堆的元素
            // 先入大根堆,  然后把大根堆元素给小根堆
            if(num <= maxQueue.peek()) {
                maxQueue.add(num);
                minQueue.add(maxQueue.poll());
            } else {
                // 如果这个数小于大根堆
                // 就直接入小根堆
                minQueue.add(num);
            }
        }


    }

    public double findMedian() {
        // 开始判断奇偶个数
        if(maxQueue.size() == minQueue.size()) {
            int num1 = maxQueue.poll() , num2 = minQueue.poll();
            maxQueue.add(num1); minQueue.add(num2);
            return (num1 + num2 ) / 2.0 ;
        }

        return  maxQueue.peek();

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */



